package 代码随想录_动态规划.基础题目;

/**
 * @author zx
 * @create 2022-05-22 15:39

 * 1.确定dp数组（dp table）以及下标的含义
 *  dp[i]：爬到第i层楼梯，有dp[i]种方法
 * 2.确定递推公式
 *  dp[i] = dp[i - 1] + dp[i - 2]
 * 3.dp数组如何初始化
 *  不考虑dp[0]如果初始化，只初始化dp[1] = 1，dp[2] = 2，然后从i = 3开始递推，这样符合dp[i]的定义。
 * 4.确定遍历顺序
 *  从递推公式dp[i] = dp[i - 1] + dp[i - 2];中可以看出，遍历顺序一定是从前向后遍历的
 * 5.举例推导dp数组
 *
 * 跳台阶扩展问题(牛客)
 * 一只青蛙一次可以跳上1级台阶,也可以跳上2级…它也可以跳上n级.求该青蛙跳上一个n级的台阶(n为正整数)总共有多少种跳法。
 *
 * 数据范围：1 ≤ n ≤ 20
 * 进阶：空间复杂度 O(1) 时间复杂度: O(1)
 */
public class 爬楼梯_70 {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 这又有难度了,这其实是一个完全背包问题(代码回想录)?????????????
     * @return
     */
    public int jumpFloorII (int number) {
        int[] dp = new int[number + 1];
        dp[0] = 1;
        for(int i = 0;i <= number;i++){
            for(int j = 1;j <= 20;j++){
                if(i - j >= 0){
                    dp[i] = dp[i] + dp[i - j];
                }
            }
        }
        return dp[number];
    }

}
